/**
 * 剑指 Offer 38. 字符串的排列
 * https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
 */
const { displayBaseArray } = require('../../libs/public');

function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {string[]} chars
 * @param {number} begin
 * @param {Set<string>} set
 */
function permutationSub(chars, begin, set) {
  if (begin === chars.length - 1) {
    set.add(chars.join(''));
    return;
  }
  const charsCopy = Array.from(chars);
  for (let i = begin; i < charsCopy.length; i += 1) {
    swap(charsCopy, begin, i);
    permutationSub(charsCopy, begin + 1, set);
  }
}

/**
 * @param {string} s
 * @return {string[]}
 */
function permutation(s) {
  const set = new Set();
  permutationSub(s.split(''), 0, set);
  return Array.from(set);
}

console.log(displayBaseArray(permutation('abc')) === '[abc,acb,bac,bca,cab,cba]');
